package algorithms.dynamicProgram;

public class LeetCode_5_2 {

    public static void main(String[] args) {
        String s = "babad";
        String s1 = "cbbd";
        String s2 = "aa";
        System.out.println(longestPalindrome(s));
        System.out.println(longestPalindrome(s1));
        System.out.println(longestPalindrome(s2));
    }

    public static String longestPalindrome(String s) {
        int maxLen = 1;
        int startIndex = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length - 1; i++) {
            int first = centerSpread(chars, i, i);
            int second = centerSpread(chars, i, i + 1);
            int curMaxLen = Math.max(first, second);
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen;
                startIndex = i - (maxLen-1)/2;
            }

        }
        return s.substring(startIndex, startIndex + maxLen);

    }

    public static int centerSpread(char[] chars, int left, int right) {
        while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
            left--;
            right++;

        }
        return right - left - 1;

    }


}
